package tree;

public class Ex236 {

    static class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
             if (root == null) return null;
             if (root == p || root == q) return root;

             //若p、q其中一个是另一个的祖先
             if (isInSubTree(p, q)) return p;
             else if (isInSubTree(q, p)) return q;

             //p.q分别在root的左右子树，因此最近祖先为根节点
            boolean l1 = isInSubTree(root.left, p), r1 = isInSubTree(root.right, q);
            if (l1 && r1) return root;
            boolean l2 = isInSubTree(root.left, q), r2 = isInSubTree(root.right, p);
            if (l2 && r2) return root;

            if (l1 && l2) return lowestCommonAncestor(root.left, p, q);
            else return lowestCommonAncestor(root.right, p, q);
        }

        // public TreeNode subTreeNode (TreeNode root, TreeNode p, TreeNode q) {

        // }

        public boolean isInSubTree (TreeNode ast, TreeNode sub) {
            if (ast == null) return false;
            if (ast == sub) return true;

            return isInSubTree(ast.left, sub) || isInSubTree(ast.right, sub);
             /* if (ast == null) return null;
             if (ast == sub) return ast;
             TreeNode res = isInSubTree(ast.left, sub);
             if (res != null) return res;
             else return isInSubTree(ast.right, sub); */
        }

       public static void main(String[] args) {
           Solution s = new Solution();
           TreeNode root = TreeUtils.createTree(new Integer[]{3,5,1,6,2,0,8,null,null,7,4});

       }
}
}
